package com.demo.v3;

public class RbTree<T extends Comparable<T>> {
    /**
     * 根节点
     */
    private RbtNode<T> mRoot;

    /**
     * 查找红黑树中指定为key的节点
     */
    public RbtNode<T> search(T key) throws Exception {
        return search(mRoot, key);
    }

    private RbtNode<T> search(RbtNode<T> x, T key) throws Exception {
        if(x == null){
            throw new Exception("key can't null");
        }
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            return search(x.right, key);
        }else if(cmp < 0){
            return search(x.left, key);
        }else{
            return x;
        }
    }

    /**
     * 插入key值到红黑树
     */
    public void insert(T key) throws Exception {
        //1. 构建黑色节点并检验空值
        RbtNode<T> node = generateBlackNodeByKey(key);
        //2. 将红黑树当作二叉查找树，节点添加到二叉查找树中，设置节点颜色为红色
        insertNodeInUnbalanceTree(node);
        //3. 按照红黑规则调整为红黑树
        balanceTreeByInsertNode(node);
    }

    /**
     * 构建黑色节点并检验空值
     * @param key
     * @return
     * @throws Exception
     */
    private RbtNode<T> generateBlackNodeByKey(T key) throws Exception {
        if(key != null){
            return new RbtNode<T>(key, RbtNode.BLACK, null, null, null);
        }else{
            //抛出异常进行测试，不建议返回null
            throw new Exception("key can't null");
        }
    }

    /**
     * 将红黑树当作二叉查找树，节点添加到二叉查找树中，设置节点颜色为红色
     */
    private void insertNodeInUnbalanceTree(RbtNode<T> node){
        //TODO wangshengkai
    }

    /**
     * 按照红黑规则调整为红黑树
     * @param node
     */
    private void balanceTreeByInsertNode(RbtNode<T> node){
        //TODO wangshengkai
    }

    /**
     * 打印红黑树
     */
    public void print(){
        //TODO wangshengkai
    }
}
